﻿using Newtonsoft.Json.Linq;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;
using System.Xml.Linq;

namespace Algorithm
{


    public static class MaxFlowEK
    {

        public static List<String> PersonCert = new List<string>();

        public static List<string> randomCert = new List<string>() { "a", "b", "c", "d", "ab", "ac", "ad", "bd", "bd", "cd", "abc", "abd", "acd", "abcd" };

        public static Random Random = new Random();
        public static async Task Run()
        {

            //for (int i = 0; i < 1000; i++)
            //{

            //    PersonCert.Add(randomCert[Random.Next(14)]);
            //}
            //Console.WriteLine($"start:{DateTime.Now}");
            //var result = CheckDemand(4, 5, 3,2, PersonCert);
            //Console.WriteLine($"end:{DateTime.Now}");
            //Console.WriteLine($"需求4A5B3C: {result}");

            var a = Task.Run(() =>
            {
                return new Tuple<decimal, decimal>(0m, 0m);
            });



            var getInvoiceStatisticsAndCollectionApplyMoneyTask = (long dataId) => {
                return Task.Run(async () => {
                    return new Tuple<decimal, decimal>(0m, decimal.Parse(dataId.ToString()));
                });
            };

            var b = await getInvoiceStatisticsAndCollectionApplyMoneyTask(2);

            //// 测试1: 可满足案例
            var people1 = new List<string> { "AC", "AD" };
            var result1 = CheckDemand(2, 1, 2, 10, people1);
            Console.WriteLine($"需求2A1B2C10D: {result1}"); // 应输出"需求已满足"

            //// 测试2: 需要调整的案例
            //var people2 = new List<string> { "AB", "AB", "B" };
            //var result2 = CheckDemand(1, 2, 0, people2);
            //Console.WriteLine($"需求1A2B: {result2}"); // 应输出"需求已满足"

            //// 测试3: 部分满足案例
            //var people3 = new List<string> { "A", "B", "C" };
            //var result3 = CheckDemand(2, 1, 0, people3);
            //Console.WriteLine($"需求2A1B: {result3}"); // 应输出"缺少A证:1, 缺少B证:0, 缺少C证:0"

            //// 测试4: 完全不可满足案例
            //var people4 = new List<string> { "A", "B", "C" };
            //var result4 = CheckDemand(3, 0, 0, people4);
            //Console.WriteLine($"需求3A: {result4}"); // 应输出"缺少A证:2, 缺少B证:0, 缺少C证:0"
            Console.WriteLine("end");
        }

        // 2. 新增结果验证方法
        private static void ValidateResult(ref JObject result, int[,] graph)
        {
            // 检查是否有A证书人员被分配为低级证书
            if (int.Parse(result["MissingA"]!.ToString()) > 0)
            {
                // 尝试将D/C/B分配转为A分配
                int convertible = graph[2, 1]; // 可转换的A容量

                if (convertible > 0)
                {
                    int recoverable = Math.Min(int.Parse(result["MissingA"]!.ToString()), convertible);
                    result["MissingA"] = int.Parse(result["MissingA"]!.ToString()) - recoverable;
                    // 将缺少量转移到最低优先级证书
                    result["MissingD"] = int.Parse(result["MissingD"]!.ToString()) + recoverable;
                }
            }
        }
        public static Object CheckDemand(int a, int b, int c,int d, List<string> people)
        {
            int totalDemand = a + b + c + d;
            int n = people.Count;

            // 边界情况处理
            if (totalDemand == 0)
                return new { IsSatisfied = true };

            //处理证书少于总需求人数也要给出少的类型
            //if (totalDemand > n)
            //{
            //    int missing = totalDemand - n;
            //    return new
            //    {
            //        IsSatisfied = false,
            //        MissingA = Math.Min(a, missing),
            //        MissingB = Math.Min(b, missing - Math.Min(a, missing)),
            //        MissingC = Math.Min(c, missing - Math.Min(a + b, missing)),
            //        MissingD = Math.Min(d, missing - Math.Min(a+b+c, missing))
            //    };
            //}

            // 节点ID分配
            const int source = 0;
            const int sink = 1;
            const int aNode = 2;
            const int bNode = 3;
            const int cNode = 4;
            const int dNode = 5;  // 新增D节点
            int firstPerson = 6;  // 人员节点起始ID相应后移

            // 使用邻接矩阵存储图
            int nodeCount = firstPerson + n;
            int[,] graph = new int[nodeCount, nodeCount];

            // 1. 源点到人员节点（容量=1）
            for (int i = 0; i < n; i++)
            {
                graph[source, firstPerson + i] = 1;
            }

            // 2. 人员节点到证书节点
            for (int i = 0; i < n; i++)
            {
                string certs = people[i];
                int personNode = firstPerson + i;

                if (certs.Contains('A')) graph[personNode, aNode] = 1;
                if (certs.Contains('B')) graph[personNode, bNode] = 1;
                if (certs.Contains('C')) graph[personNode, cNode] = 1;
                if (certs.Contains('D')) graph[personNode, dNode] = 1;
            }
            // 3. 证书节点到汇点
            graph[aNode, sink] = a;
            graph[bNode, sink] = b;
            graph[cNode, sink] = c;
            graph[dNode, sink] = d;

            // 计算最大流
            int maxFlow = MaxFlow(graph, source, sink, nodeCount);

            if (maxFlow == totalDemand)
            {
                return new { IsSatisfied = true };
            }
            else
            {
                // 计算各证书实际分配数量
                int actualA = a - graph[aNode, sink];
                int actualB = b - graph[bNode, sink];
                int actualC = c - graph[cNode, sink];
                int actualD = d - graph[dNode, sink];
                var result = JObject.FromObject(new
                {
                    IsSatisfied = false,
                    MissingA = a - actualA,
                    MissingB = b - actualB,
                    MissingC = c - actualC,
                    MissingD = d - actualD
                });
                ValidateResult(ref result, graph);
                return result;
            }
        }

        // Edmonds-Karp算法实现
        private static int MaxFlow(int[,] graph, int source, int sink, int nodeCount)
        {
            int maxFlow = 0;
            int[] parent = new int[nodeCount];

            // 持续寻找增广路径
            while (BFS(graph, source, sink, parent, nodeCount))
            {
                // 计算路径最小容量
                int pathFlow = int.MaxValue;
                for (int v = sink; v != source; v = parent[v])
                {
                    int u = parent[v];
                    pathFlow = Math.Min(pathFlow, graph[u, v]);
                }

                // 更新边和反向边
                for (int v = sink; v != source; v = parent[v])
                {
                    int u = parent[v];
                    graph[u, v] -= pathFlow;
                    graph[v, u] += pathFlow;  // 关键：增加反向边容量
                }

                maxFlow += pathFlow;
            }
            return maxFlow;
        }

        // BFS查找增广路径
        private static bool BFS(int[,] graph, int source, int sink, int[] parent, int nodeCount)
        {
            bool[] visited = new bool[nodeCount];
            Queue<int> queue = new Queue<int>();

            queue.Enqueue(source);
            visited[source] = true;
            parent[source] = -1;

            while (queue.Count > 0)
            {
                int u = queue.Dequeue();

                for (int v = 0; v < nodeCount; v++)
                {
                    // 找到未访问且有容量的节点
                    if (!visited[v] && graph[u, v] > 0)
                    {
                        parent[v] = u;
                        visited[v] = true;
                        queue.Enqueue(v);

                        if (v == sink) return true;
                    }
                }
            }
            return false;
        }

    }
}
